package tree;

/**
 * 给你二叉搜索树的根节点 root ，该树中的两个节点被错误地交换。请在不改变其结构的情况下，恢复这棵树。
 */
class RecoverBST_99 {
    // 二叉搜索树中序遍历的话应该是一个从小到大排序好的数组
    // 分别记录排序错误的大值节点和小值节点，2个节点是相邻的？前一个节点大于后面一个节点，maxNode在前，minNode在后
    TreeNode minNode = null;
    TreeNode maxNode = null;
    TreeNode preNode = new TreeNode(Integer.MIN_VALUE);
    public void recoverTree(TreeNode root) {
        inorderTraversal(root);
        if (minNode != null && maxNode != null) {
            int tmp = minNode.val;
            minNode.val = maxNode.val;
            maxNode.val = tmp;
        }
    }

    public void inorderTraversal(TreeNode root) {
        if (root == null) {
            return;
        }
        inorderTraversal(root.left);

        // 如果前面一个节点值大于后面一个节点，说明是错误排序的
        // 例如 6 2 3 4 5 1 7，需要6和1互换，maxNode的值只需要记录一次，而minNode却需要一直更新到不满足preNode.val > root.val
        if (preNode.val > root.val) {
            if (maxNode == null) {
                maxNode = preNode;
            }
//            maxNode = preNode; 不能每次都更新
            minNode = root;
        }
        preNode = root;
        inorderTraversal(root.right);
    }
}
